package edu.qd.learn.newchapter.chapter04;

import java.util.*;

/**
 * @author 布衣
 */
public class Question02 {

    /**
     * 十大排序算法  ：
     * 冒泡排序、选择排序、插入排序、希尔排序、快速排序、
     * 归并排序、堆排序、基数排序、计数排序、桶排序、
     */


    public static void bubbleSort(int[] a) {
        for (int i1 = 0; i1 < a.length; i1++) {
            for (int i = 0; i < a.length - 1 - i1; i++) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                }
            }
        }

    }

    public static void main(String[] args) {
        // 容器  集合
        Vector<Student> v = new Vector<>();
        v.add(new Student(1, "张三", 80));
        v.add(new Student(2, "李四", 90));
        v.add(new Student(3, "王五", 70));
        v.sort((x,y)->(int)(x.getScore()-y.getScore()));

        Student[] ss = new Student[4];

        ss[0] = new Student(1, "张三", 80);
        ss[1] = new Student(2, "李四", 90);
        ss[2] = new Student(3, "王五", 70);
        ss[3] = new Student(4, "隗一", 69);

//    比较器  :Comparator
//    比较接口 Comparable : 当一个类实现此接口并重写里面的compareTo方法就可以进行排序 了Arrays.sort();
//        Comparable
//        Comparator
        Arrays.sort(ss, (x, y) -> (int) (x.getScore() - y.getScore()));
        System.out.println(Arrays.toString(ss));

        int[] a = {3, 2, 4, 1, 5, 7, 9, 8};
        quickSort(a);
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);
        //找个图  ： 一会自己写一遍  ()
        System.out.println(Arrays.toString(a));
        bubbleSort(a);
        System.out.println(Arrays.toString(a));

    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    public static void quickSort(int[] as, int left, int right) {

        int begin = left, end = right;
        if (left >= right) {
            return;
        }
        //最左  随机  中间
//        int basePoint = (left + right) >>> 1;
//        int basePoint = left;
//            [0,1)
//        5 -20  random()*15 +5
//        3+{x[0,1)}}
//          Left3-right18
        int basePoint = (int) (Math.random() * Math.abs(left - right + 1)) + left;
        while (left < right) {

            while (left < right && as[basePoint] > as[left]) {
                //左指针
                left++;
            }

            while (left < right && as[basePoint] < as[right]) {
                //右指针
                right--;
            }

            int temp = as[left];
            as[left] = as[right];
            as[right] = temp;
        }

        //交换基准与left

        int temp = as[left];
        as[left] = as[basePoint];
        as[basePoint] = temp;

        quickSort(as, begin, basePoint - 1);
        quickSort(as, basePoint + 1, end);
    }


    //1 : 生成57 - 89的正整数  Math.random();


}
